464E - The Classic Problem - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

template<typename T> inline void in(T &s) {
	char c = getchar(); int f = 1; s = 0;
	while (!isdigit(c)) { if (c == '-') f = -1; c = getchar(); }
	while (isdigit(c)) s = (s << 3) + (s << 1) + (c ^ 48), c = getchar();
	if (f < 0) s = -s;
}

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;

const int N = 1e5 + 5;
const int B = 6400, H = 16;
const ull mod = 1e9 + 7;
const ull mod1 = 62538268673, bas1 = 294967297;
const ull mod2 = 62538268651, bas2 = 294967259;

ull pl[N], pl1[N];
ull p26[N];
ull p[N];

namespace CT {
	const int P = 1e7 + 5;
	
	struct tree {
		int ls, rs;
		int c;
		ull v, v1, v2, v3, v4;
	} t[P];
	int cnt;
	
	int build(int l, int r) {
		int o = ++cnt;
		if (l == r)
			return o;
		int mid = (l + r) >> 1;
		t[o].ls = build(l, mid);
		t[o].rs = build(mid + 1, r);
		return o;
	}
	void pu(int o, int l, int r) {
		int mid = (l + r) >> 1;
		t[o].v1 = t[t[o].ls].v1 ^ t[t[o].rs].v1;
		t[o].v2 = (t[t[o].rs].v2 * p26[mid - l + 1] % mod + t[t[o].ls].v2) % mod;
		// t[o].v3 = (t[t[o].rs].v3 * bas2 % mod2 + (t[t[o].ls].v3 ^ pl1[mid]) + pl[mid]) % mod2;
		// t[o].v4 = (t[t[o].rs].v4 * bas1 % mod1 + (t[t[o].ls].v4 ^ pl[mid]) + pl1[mid]) % mod1;
		t[o].v3 = (t[t[o].rs].v3 * bas2 % mod2 + t[t[o].ls].v3) % mod2;
		t[o].v4 = (t[t[o].rs].v4 * bas1 % mod1 + t[t[o].ls].v4) % mod1;
		t[o].c = t[t[o].ls].c + t[t[o].rs].c;
	}
	pair<int, int> mdf(int raw, int l, int r, int u, ull w) {
		int o = ++cnt;
		t[o] = t[raw];
		ull rawv = t[o].v;
		t[o].v += w;
		t[o].v %= p[H];
		t[o].v1 = t[o].v;
		int tmp = t[o].v, ccc = 0;
		t[o].v2 = 0;
		while (tmp) {
			t[o].v2 = (t[o].v2 + tmp % 26 * p26[ccc] % mod) % mod;
			++ccc;
			tmp /= 26;
		}
		t[o].v3 = t[o].v % mod2;
		t[o].v4 = t[o].v % mod1;
		t[o].c = __builtin_popcount(t[o].v);
		if (l == r)
			return make_pair(o, (int)(rawv > t[o].v));
		int mid = (l + r) >> 1;
		pair<int, int> g;
		if (u <= mid)
			g = mdf(t[raw].ls, l, mid, u, w), t[o].ls = g.first;
		else
			g = mdf(t[raw].rs, mid + 1, r, u, w), t[o].rs = g.first;
		pu(o, l, r);
		return make_pair(o, g.second);
	}
	int judge(int x, int y) {
		return t[x].v == t[y].v && t[x].v1 == t[y].v1 && t[x].v2 == t[y].v2 && t[x].v3 == t[y].v3 && t[x].v4 == t[y].v4 && t[x].c == t[y].c;
	}
	int cmp(int x, int y, int l, int r) { // x > y ??
		if (l == r)
			return t[x].v > t[y].v;
		int mid = (l + r) >> 1;
		if (judge(t[x].rs, t[y].rs))
			return cmp(t[x].ls, t[y].ls, l, mid);
		else
			return cmp(t[x].rs, t[y].rs, mid + 1, r);
	}
	ull qry(int o, int l, int r, int u) {
		if (l == r)
			return t[o].v;
		int mid = (l + r) >> 1;
		if (u <= mid)
			return qry(t[o].ls, l, mid, u);
		else
			return qry(t[o].rs, mid + 1, r, u);
	}
	int mdf(int raw, int u, ull w) {
		auto [o, op] = mdf(raw, 1, B, u, w);
		while (op) {
			++u;
			auto [_o, _op] = mdf(o, 1, B, u, (ull)1);
			o = _o, op = _op;
		}
		return o;
	}
}

int r[N];

struct node {
	int u, a;
	node (int _u = 0, int _a = 0) {
		u = _u, a = _a;
	}
	bool operator < (const node & g) const {
		return CT::cmp(a, g.a, 1, B);
	}
};

int n, m;
int s, t;
vector<pair<int, int> > g[N];
priority_queue<node> q;
int vis[N];
int pth[N], las[N];

pair<int, ull> get(int x) {
	return make_pair(x / H + 1, p[x % H]);
}
void trip(int o) {
	if (las[o])
		trip(las[o]);
	printf("%d ", o);
}

mt19937 rnd(time(0));

int main() {
	p26[0] = 1;
	for (int i = 1; i <= B; ++i)
		p26[i] = p26[i - 1] * (ull)26 % mod;
	for (int i = 1; i <= B; ++i)
		pl[i] = 1ll * rnd() * rnd() % mod1;
	for (int i = 1; i <= B; ++i)
		pl1[i] = 1ll * rnd() * rnd() % mod1;
	p[0] = 1;
	for (int i = 1; i <= H; ++i)
		p[i] = p[i - 1] + p[i - 1];
	in(n), in(m);
	for (int i = 1; i <= m; ++i) {
		int u, v, w;
		in(u), in(v), in(w);
		g[u].emplace_back(make_pair(v, w));
		g[v].emplace_back(make_pair(u, w));
	}
	in(s), in(t);
	r[s] = CT::build(1, B);
	q.push(node(s, r[s]));
	pth[s] = 1;
	while (!q.empty()) {
		auto tp = q.top();
		int u = tp.u;
		int raw = tp.a;
		q.pop();
		if (vis[u])
			continue;
		vis[u] = 1;
		for (auto [v, w] : g[u]) {
			if (vis[v])
				continue;
			auto [id, ww] = get(w);
			int o = CT::mdf(raw, id, ww);
			if (!r[v] || CT::cmp(r[v], o, 1, B)) {
				r[v] = o;
				q.push(node(v, o));
				las[v] = u;
				pth[v] = pth[u] + 1;
			}
		}
	}
	if (!r[t]) {
		puts("-1");
		return 0;
	}
	ull ans = 0;
	for (int i = B; i >= 1; --i) {
		ull w = CT::qry(r[t], 1, B, i);
		w %= mod;
		ans = ans * p[H] % mod;
		ans = (ans + w) % mod;
	}
	printf("%llu\n", ans);
	printf("%d\n", pth[t]);
	trip(t);
	return 0;
}